package oj;

public class LC338 {
    public int[] countBits(int n) {
        int[] arr=new int[n+1];
        for(int i=0;i<=n;i++){
            arr[i]=countOnes(i);
        }
        return arr;
    }
    //Brian Kernighan算法
    private int countOnes(int n){
        int count=0;
        while(n>0){
            n=n&(n-1);
            count++;
        }
        return count;
    }


//    public int[] countBits(int n) {
//        int[] arr=new int[n+1];
//        for(int i=0;i<=n;i++){
//            int count=0;
//            for(int j=i;j!=0;j/=2){
//                count+=j%2;
//            }
//            arr[i]=count;
//        }
//        return arr;
//    }
}
